En
Calculabilité, la fonction de Sudan est un exemple de
Fonction récursive mais non primitive récursive. Ceci est aussi le cas de la bien plus connue
Fonction d'Ackermann.
Elle fut conçue en 1927 par le mathématicien roumain Gabriel Sudan élève de David Hilbert.
Définition
F 0 (x, y) = x+y, F n + 1 (x, 0) = x, n ≥ 0
F n + 1 (x, y+1) = F n (F n + 1 (x, y), F n + 1 (x, y) + y + 1), n ≥ 0.
Voir aussi